#include <iostream>
#include "Stack.h"
using namespace std;

#define MaxVertexNum 100 // 图中顶点数目最大值
typedef int VertexType;

/// @brief 边表节点
typedef struct ArcNode
{
    int adjvex;              // 该弧所指向的顶点的位置
    struct ArcNode *nextarc; // 指向下一条弧的指针
    // InfoType info;// 网的边权值
} ArcNode;

/// @brief 顶点表节点
typedef struct VNode
{
    VertexType data;   // 顶点信息
    ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MaxVertexNum];

/// @brief 图：以邻接表存储的图类型
typedef struct
{
    AdjList vertices;   // 邻接表
    int vexnum, arcnum; // 图的定点数和弧数
} Graph;

SqStack S;
/// @brief 当前顶点入度
int indegree[];
/// @brief 记录拓扑序列
int print[];

bool TopologicalSort(Graph G)
{
    InitStack(S); // 初始化栈，存储入度为0的顶点
    for (int i = 0; i < G.vexnum; i++)
    {
        if (indegree[i] == 0)
        {
            Push(S, i); // 将所有入度为0的顶点进栈
        }
        int count = 0;      // 计数，记录当前已经输出的顶点数
        while (!IsEmpty(S)) // 栈不空，则存在入度为0的顶点
        {
            Pop(S, i);          // 栈顶元素出栈
            print[count++] = i; // 输出顶点i
            int v = -1;
            // 将所有i指向的顶点的入度减1，并且将入度为0的顶点压入栈S
            for (ArcNode *p = G.vertices[i].firstarc; p; p = p->nextarc)
            {
                v = p->adjvex;
                if (!(--indegree[v]))
                {
                    Push(S, v); // 入度为0，则入栈
                }
            }
        } // while
        if (count < G.vexnum)
        {
            return false; // 排序失败，有向图中有回路
        }
        else
        {
            return true; // 拓扑排序失败
        }
    }
}

///////////////////////逆拓扑排序的实现（DFS算法）///////////////////////////////////////////////
int visited[];
int FirstNeighbor(Graph G, int v)
{
    return 0;
}
int NextNeighbor(Graph G, int v, int w)
{
    return 0;
}
/// @brief 从顶点v出发，深度优先遍历图G
/// @param G
/// @param v
void DFS(Graph G, int v)
{
    // visit(v);//访问顶点v
    visited[v] = true; // 设已访问标记
    for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
    {
        if (!visited[w])
        { // w为v的尚未访问的邻接顶点
            DFS(G, w);
        }
    }
    printf("%d", v); // 输出顶点
}

/// @brief 对图G进行深度优先遍历
/// @param G
void DFSTraverse(Graph G)
{
    for (int v = 0; v < G.vexnum; ++v)
    {
        visited[v] = false; // 初始化已访问标记数据
    }
    for (int v = 0; v < G.vexnum; ++v)
    { // 本代码中是从v=0开始遍历
        if (!visited[v])
        {
            DFS(G, v);
        }
    }
}